package 牛客网在线编程题库;

/**
 * 输入一个链表，反转链表后，输出新链表的表头。
 * 示例1
 * 输入
 * 复制
 * {1,2,3}
 * 返回值
 * 复制
 * {3,2,1}
 */

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class _反转链表 {
    public ListNode ReverseList(ListNode head){
        // 新链表头部
        ListNode newNode = new ListNode(0);
        // 遍历指针
        ListNode cur = head;
        // 遍历指针的下一个结点
        ListNode next = null;
        // 开始遍历
        while (cur != null) {
            // 指向遍历指针的下一个结点
            next = cur.next;
            // 将当前指针连接到新链表
            cur.next = newNode.next;
            newNode.next = cur;
            // 将遍历指针直接插到原链表的下一个结点
            cur = next;
        }
        return newNode.next;
    }
}
